#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 500 * 500 + 10;
int a, n;
int pos;
struct node
{
    int x;
    int y;
    int z;
}s[N];
int fa[N];
int find(int x)
{
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
int cnt;
int ret;
bool cmp(node& s1, node& s2)
{
    return s1.z < s2.z;
}
void kk()
{
    sort(s + 1, s + pos + 1, cmp);
    for (int i = 1; i <= pos; i++)
    {
        int x = s[i].x;
        int y = s[i].y;
        int z = s[i].z;
        int fx = find(x);
        int fy = find(y);
        if (fx != fy)
        {
            cnt++;
            ret += z;
            fa[fx] = fy;
        }
    }
}
int main()
{
    cin >> a >> n;
    for (int i = 1; i <= n; i++)
    {
        fa[i] = i;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            int k;
            cin >> k;
            if (a < k || i >= j || k == 0)
            {
                continue;
            }
            pos++;
            s[pos].x = i;
            s[pos].y = j;
            s[pos].z = k;
        }
    }
    kk();
    cout << ret + (n - cnt) * a << endl;
    return 0;
}